package com.xubaohua.八大排序;

/**
 * @program: 直接插入排序
 * @description:
 * @author: 许宝华
 * @create: 2022-04-16 18:34
 */

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 直接插入排序的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含n-1个元素
 * 排序过程中每次从无序表中取出第一个元素，把它的排序码一次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] arr = new int[]{105,56,1,3};


        System.out.println("排序前"+ Arrays.toString(arr));
//        insertSort(arr);

        int[] arrMax = new int[50000];
        for (int i = 0; i <50000 ; i++) {
            arrMax[i] = (int)(Math.random() * 8000000);
        }

        Date date = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
        String format = simpleDateFormat.format(date);
        System.out.println(format);

        insertSort1(arrMax);

        Date date1 = new Date();
        String format1 = simpleDateFormat.format(date1);
        System.out.println(format1);

    }

    /**
     * 插入排序推导过程
     * @param arr
     */
    private static void insertSort(int[] arr){

        //定义待插入的数
        int insertVal = arr[1];
        int insertIndex = 1-1;
        /*
            insertIndex >= 0确保数组不越界
            insertVal < arr[insertIndex]证明待插入元素还没有找到合适位置，为其寻找合适位置
         */
        while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
            arr[insertIndex+1] = arr[insertIndex];
            insertIndex--;
        }
        arr[insertIndex+1] = insertVal;

        System.out.println("第一轮排序"+ Arrays.toString(arr));

        insertVal = arr[2];
        insertIndex = 2-1;
        /*
            insertIndex >= 0确保数组不越界
            insertVal < arr[insertIndex]证明待插入元素还没有找到合适位置，为其寻找合适位置
         */
        while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
            arr[insertIndex+1] = arr[insertIndex];
            insertIndex--;
        }
        arr[insertIndex+1] = insertVal;

        System.out.println("第二轮排序"+ Arrays.toString(arr));

        insertVal = arr[3];
        insertIndex = 3-1;
        /*
            insertIndex >= 0确保数组不越界
            insertVal < arr[insertIndex]证明待插入元素还没有找到合适位置，为其寻找合适位置
         */
        while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
            arr[insertIndex+1] = arr[insertIndex];
            insertIndex--;
        }
        arr[insertIndex+1] = insertVal;

        System.out.println("第三轮排序"+ Arrays.toString(arr));
    }


    /**
     * 插入排序优化
     * @param arr
     */
    private static void insertSort1(int[] arr){
        for (int i = 1; i <= arr.length-1; i++) {
            //定义待插入的数
            int insertVal = arr[i];
            int insertIndex = i-1;
            /*
                insertIndex >= 0确保数组不越界
                insertVal < arr[insertIndex]证明待插入元素还没有找到合适位置，为其寻找合适位置
            */
            while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex+1] = arr[insertIndex];
                insertIndex--;
            }
            if (insertIndex+1 != i) {
                arr[insertIndex+1] = insertVal;
            }
//            System.out.println("第"+i+"轮排序"+ Arrays.toString(arr));

        }
    }
}
